|
| creator |
Rantzau, Ralf
| | Shapiro, Leonard
| | Mitschang, Bernhard
| | Wang, Quan
| | date |
2002-03
| | | | description |
Queries containing universal quantification are used in many
applications, including business intelligence applications. Several
algorithms have been proposed to implement universal quantification
efficiently. These algorithms are presented in an isolated manner in
the research literature - typically, no relationships are shown
between them. Furthermore, each of these algorithms claims to be
superior to others, but in fact each algorithm has optimal
performance only for certain types of input data. In this paper, we
present a comprehensive survey of the structure and performance of
algorithms for universal quantification. We introduce a framework
for classifying all possible kinds of input data for universal
quantification. Then we go on to identify the most efficient
algorithm for each such class. One of the input data classes has not
been covered so far. For this class, we propose several new
algorithms. For the first time, we are able to identify the optimal
algorithm to use for any given input dataset. These two
classifications of input data and optimal algorithms are important
for query optimization. They allow a query optimizer to make the
best selection when optimizing at intermediate steps for the
quantification problem.
| | format |
application/postscript
| | 1005887 Bytes | |